#include <assert.h>
#include <malloc.h>
#include <stdio.h>
#include <string.h>
#include "tree.h"

/*  WMN 10/06    
    General purpose tree for storing string-labeled data objects.
    Any data structure labeled by a string can be stored. 

    Tree structure:

    Root: key = 0, data = 0
    Node: key = char, data = 0 (if no seq matches); data != 0 (a seq matches)

    E.g., sequences AXW0, AXW005 make the following tree:

    root
        Key:A  data:0
            Key:X  data:0
                Key:W  data:0
                    Key:'0'  data:nonzero
                        Key:'0'  data:0
                            Key:'5'  data:nonzero 

    User must implement a routine to free the data structures and pass
    it to the tree functions which do deletions. 

    Child nodes are linked alphabetically so a depth-first traverse
    is in alphabetic order. 
*/

/* It would have been better to use the AceDB arrays with glib
    hashes to detect duplicates when loading. 
 */
    

void clear_fpc_tree(FPC_TREE* ptree, void (*data_free)(void** pdata))
{
    assert(ptree);
    if (ptree->child != 0)
    {
        clear_fpc_tree(ptree->child, data_free);   
        free(ptree->child);    
        ptree->child = 0; 
    }
    if (ptree->sibling != 0)
    {
        clear_fpc_tree(ptree->sibling, data_free);
        free(ptree->sibling);
        ptree->sibling = 0; 
    } 
    if (ptree->pdata)
    { 
        if (data_free)
        {
            (*data_free)((void**)&(ptree->pdata));      
        }  
        ptree->pdata = 0;
    }       
}
int fpc_tree_has_content(FPC_TREE* ptree)
{
    return (ptree->child != 0 ? 1 : 0);
}

/* Insert new node, keep alphabetic order of keys */
void _fpc_tree_insert_node(FPC_TREE* ptree, void* pdata, char* label, int level)
{
    FPC_TREE *pnext, *pprev, *pnew;

    assert(ptree);
    assert(pdata);

    if (level == strlen(label))
    {
        /* this is the target node */
        if (ptree->pdata)
        {
            //fprintf(stderr,"Duplicate insertion for %s\n",label);
        }
        ptree->pdata = pdata;
    }
    else
    {
        pnext = ptree->child;
        pprev = 0;
        while (pnext)
        {
            if (pnext->key == label[level])
            {
                _fpc_tree_insert_node(pnext,pdata,label,level+1);
                return;
            }    
            else if (pnext->key > label[level])
            {
                break;
            }
            pprev = pnext;
            pnext = pnext->sibling;
        }   
        /* No matches - we have to add a child */
        pnew = (FPC_TREE*)malloc(sizeof(FPC_TREE));
        pnew->key = label[level];
        pnew->pdata = 0;
        pnew->child = 0;
        pnew->sibling = pnext;
        if (pprev)
        {
            pprev->sibling = pnew;
        }
        else
        {
            ptree->child = pnew;
        }
        _fpc_tree_insert_node(pnew,pdata,label,level+1);
    }
}

void fpc_tree_insert_node(FPC_TREE* ptree, void* pdata, char* label)
{
    _fpc_tree_insert_node(ptree, pdata, label, 0);
}

void* _fpc_tree_find_data(FPC_TREE* ptree, char* label, int level)
{
    FPC_TREE* pnext;

    assert(ptree);

    if (level == strlen(label))
    {
        /* this is the target node */
        return ptree->pdata;
    }
    else if (ptree->child)
    {
        pnext = ptree->child;
        while (pnext)
        {
            if (pnext->key == label[level])
            {
                return _fpc_tree_find_data(pnext,label,level+1);
            }    
            else if (pnext->key > label[level])
            {
                break;
            }
            pnext = pnext->sibling;
        }   
    }
    /* not the matching node and no matching child nodes!! */
    return 0;
}


void* fpc_tree_find_data(FPC_TREE* ptree, char* label)
{
    void* pret;
    pret = _fpc_tree_find_data(ptree,label,0);
    if (!pret)
    {
        //fprintf(stderr,"Failed to find %s\n", label);
    }
    return pret;
}

int _fpc_tree_remove_data(FPC_TREE* ptree, char* label, int level, void (*data_free)(void** pdata))
{
    FPC_TREE *pnext, *pprev;
    int ret = 0;

    assert(ptree);

    if (level == strlen(label))
    {
        /* this is the target node */
        if (ptree->pdata)
        {
            if (data_free)
            {
                (*data_free)(&ptree->pdata);
            }
            ptree->pdata = 0;
            ret = 1;
        }
    }
    else if (ptree->child)
    {
        pnext = ptree->child;
        pprev = 0;
        while (pnext)
        {
            if (pnext->key == label[level])
            {
                ret = _fpc_tree_remove_data(pnext,label,level+1,data_free);
                /* if the child now has empty data and no children, remove it */
                if (!pnext->pdata && !pnext->child)
                {
                    if (pprev)
                    {
                        pprev->sibling = pnext->sibling;
                    }
                    else
                    {
                        ptree->child = pnext->sibling;
                    }
                    free(pnext);
                }
                break;
            }
            else if (pnext->key > label[level])
            {
                break;
            }
            pprev = pnext;
            pnext = pnext->sibling;
        }   
    }
    else
    {
        /* Sequence not found! */
        ret = 0;
    }
    return ret;
}

int fpc_tree_remove_data(FPC_TREE* ptree, char* label, void (*data_free)(void** pdata))
{
    int ret;
    ret = _fpc_tree_remove_data(ptree,label,0,data_free);
    if (!ret)
    {
        //fprintf(stderr,"Failed to find %s\n", label);
    }
    return ret;
}


void _fpc_tree_count_filled_nodes(FPC_TREE* ptree, int level, int* pcount)
{
    assert(ptree);   
    if (ptree->pdata)
    {
        (*pcount)++;
    }

    if (ptree->child != 0)
    {
        _fpc_tree_count_filled_nodes(ptree->child,level+1,pcount);        
    }
    if (ptree->sibling != 0)
    {
        _fpc_tree_count_filled_nodes(ptree->sibling,level,pcount);
    } 
}

int fpc_tree_count_filled_nodes(FPC_TREE* ptree)
{
    int count = 0;
    _fpc_tree_count_filled_nodes(ptree,0,&count);
    return count;
}

void dump_fpc_tree(FPC_TREE* ptree, int level)
{
    int i;

    assert(ptree);
    for(i = 0; i < level; i++)
    {
        printf("  ");
    }    
    if (ptree->pdata)
    {
        printf("%c D\n",ptree->key);
    }
    else
    {
        printf("%c\n",ptree->key);
    }
    if (ptree->child != 0)
    {
        dump_fpc_tree(ptree->child,level+1);        
    }
    if (ptree->sibling != 0)
    {
        dump_fpc_tree(ptree->sibling,level);
    } 
}


void init_fpc_tree(FPC_TREE* ptree)
{
    assert(ptree);
    ptree->pdata = 0;
    ptree->key = 0;
    ptree->child = 0;
    ptree->sibling = 0;
}

FPC_TREE* fpc_tree_next_node(FPC_TREE* pnode, FPC_STACK* pstack)
{
    FPC_TREE* curnode;

    assert(pstack);
    assert(pnode);

    if (pnode->child)
    {
        fpc_stack_push(pstack,pnode);
        return pnode->child;
    }
    if (pnode->sibling)
    {
        fpc_stack_push(pstack,pnode);
        return pnode->sibling;
    }
    curnode = pnode;
    pnode = fpc_stack_pop(pstack);
    while (pnode)
    {
        if (pnode->sibling && !(pnode->sibling == curnode))
        {
            fpc_stack_push(pstack,pnode);
            return pnode->sibling;
        }
        curnode = pnode;    
        pnode = fpc_stack_pop(pstack);    
    }
    return pnode;
}

/***********************************************
    Stack functions
***********************************************/

/* A stack is needed to traverse a tree...unfortunately */

void fpc_stack_init(FPC_STACK* pstack)
{
    assert(pstack);
    pstack->node = 0;
    pstack->next = pstack;
    pstack->prev = 0;
}

void fpc_stack_destroy(FPC_STACK* pstack)
{
    FPC_STACK *ps, *ps1;

    assert(pstack);
    ps = pstack->next;
    while (ps->node)
    {
        ps1= ps->next;  
        free(ps);  
        ps = ps1;    
    }   
}

void fpc_stack_push(FPC_STACK* pstack, FPC_TREE* node)
{
    FPC_STACK* new;
    assert(node);
    new = (FPC_STACK*)malloc(sizeof(FPC_STACK));     
    new->node = node;
    new->next = pstack;
    new->prev = pstack->prev;
    if (pstack->prev)
    {
        pstack->prev->next = new;
    }
    pstack->prev = new;   
    assert(pstack->prev->node);     
}

FPC_TREE* fpc_stack_pop(FPC_STACK* pstack)
{
    FPC_TREE* pret = 0;
    FPC_STACK* prelease;

    if (pstack->prev)
    {
        pret = pstack->prev->node;
        prelease = pstack->prev;
        if (pstack->prev->prev)
        {
            pstack->prev->prev->next = pstack;
        }
        pstack->prev = pstack->prev->prev;
        free(prelease);
    }
    return pret;
}
